package Top_Interview_Questions_Review._001Tree;

import Top_Interview_Questions_Review._001Tree.Supple.TreeNode;

/**
 * @Author: 吕庆龙
 * @Date: 2020/2/10 11:15
 * <p>
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/java-dfs-jian-zhi-9ms9244-by-lava-4/
 * 这题画图也没画明白为啥要这样写
 */
public class _0236 {

    public static void main(String[] args) {
        _0236 test = new _0236();

        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(6);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(0);
        TreeNode node6 = new TreeNode(8);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(4);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node4.left = node7;
        node4.right = node8;

        TreeNode res = test.lowestCommonAncestor(root, node3, node8);
        System.out.println(res);

    }

    /**
     *              3
     *           /    \
     *          5      1
     *        /  \   /  \
     *       6   2  0    8
     *          / \
     *         7  4
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归结束条件为找到了 p、q 节点，或者后续没有节点了
        if (root == null || root == p || root == q)
            return root;

        // 递归遍历左右子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果 root 节点左右子树中，都查找出了 p、q 节点，那么说明 root 节点就是最近的公共节点
        if (left != null && right != null)
            return root;
        // 否则，只要不为 null 的一方就是最近的公共节点，因为它是最先被查出来的
        return left != null ? left : right;
    }

    /**
     * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //1.当left和 right同时为空:说明 root的左/右子树中都不包含 p,q返回 null
        if(left == null && right == null)
            return null;
        //3.当left为空,right不为空:p,q都不在root的左子树中,直接返回right。具体可分为两种情况：
        //3-1.p,q其中一个在root的右子树中，此时right指向p（假设为p）；
        //3-2.p,q两节点都在root的右子树中，此时的right指向最近公共祖先节点 ；
        if(left == null) return right;
        //4.与3同理
        if(right == null) return left;
        //2.当left和right同时不为空:说明p,q分列在root的异侧（分别在左/右子树）,因此root为最近公共祖先,
        // 返回root
        return root; // 2. if(left != null and right != null)
    }

    /**
     * 情况 1，如果p和q都在以root为根的树中，那么left和right一定分别是p和q（从 base case 看出来的）。
     *
     * 情况 2，如果p和q都不在以root为根的树中，直接返回null。
     *
     * 情况 3，如果p和q只有一个存在于root为根的树中，函数返回该节点。
     */
    TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        // base case
        if (root == null) return null;
        if (root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor2(root.left, p, q);
        TreeNode right = lowestCommonAncestor2(root.right, p, q);
        // 情况 1
        if (left != null && right != null) {
            return root;
        }
        // 情况 2
        if (left == null && right == null) {
            return null;
        }
        // 情况 3
        return left == null ? right : left;
    }



}
